package leetcode_41_60;

public class canJump_55 {
    /**
     * 非负整数数组 nums ，最初位于数组的 第一个下标 。
     * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
     * 判断你是否能够到达最后一个下标
     * @param nums
     * @return
     */
    public boolean canJump(int[] nums) {
        /*
        别想那么多，就挨着跳吧
        2ms  86%
         */
        //距离
        int result = 0;
        // 从0开始往后跳
        for (int i = 0; i < nums.length; i++) {
            // 当前点能达到最远距离
            int temp = i + nums[i];
            // 之前最远距离，与当前点最远距离取最大值
            result = Math.max(temp, result);
            //超出范围，true
            if (result >= nums.length - 1) {
                return true;
            }
            //没跳动
            if (result <= i) {
                return false;
            }
        }
        return true;
    }

    /**
     * 高手思路
     * 倒序查找0，看能否跳过去每一个0。
     */
    public boolean canJump2(int[] nums) {
        if(nums.length==1)return true;
        int count=0;
        for (int i = nums.length-2; i >= 0; i--) { //最后一个不用考虑
            if(nums[i] <= count ){
                count++;           //需要跨越的距离
            }else
                count=0;
        }
        return count==0;
    }
}
